package main

func numPrimeArrangements(n int) int {
	// 找出所有的质数的个数
	primeNum := 0
	for i := 2; i <= n; i++ {
		if isPrime(i) {
			primeNum++
		}
	}
	// 把质数的排列数 * 非质数的排列数便是结果
	return (factorial(primeNum) * factorial(n-primeNum)) % (1e9 + 7)
}

func isPrime(n int) bool {
	if n <= 1 {
		return false
	}

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func factorial(n int) int {
	if n == 0 {
		return 1
	}
	res := 1
	for i := 1; i < n+1; i++ {
		res *= i
		res %= (1e9 + 7)
	}
	return res
}
